package com.lanqiao.recursionAndRecursion;

/*
*   如图数字三角形。如下所示为一个数字三角形。请编一个程序计算从顶到底的某处的一条路径，使该路径所经过的数字总和最大。只要求输出总和。　
    输入：
    5
    7
    3 8
    8 1 0
    2 7 4 4
    4 5 2 6 5
* */

import java.util.Scanner;

/**
 * @author kjx
 */
public class NumberTriangle {
    //这个题用反向递推即可

    static int[][] a = new int[101][101];

    public static void main(String[] args) {

        Scanner in = new Scanner(System.in);

        int n;
        n = in.nextInt();

        //输入数字三角形的值（这里为了方便就直接从1开始了）
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= i; j++) {
                a[i][j] = in.nextInt(); //输入原始数据
            }
        }

        //递推开始
        for (int i = n - 1; i >= 1; i--)
            for (int j = 1; j <= i; j++)
                a[i][j] += Math.max(a[i + 1][j], a[i + 1][j + 1]);


        System.out.println(a[1][1]);
    }
}
